package com.dylan.历史.算法;

/**
 * Created by Dylan on 2018/8/2.
 *
 * 题目: 计算一个字符串分割为回文字符串的最小分割数
 * 回文字符串实例: "A","AA","ABA","ABCBA"
 * 字符串分割为回文字符串的最小分割数实例:
 * "ABA" 0
 * "ACDCDCDAD" 2 "A","CDCDC","DAD"
 *
 * 计算过程:
 * 1.假设j位置出在i与len-1的位置之间(i<=j<len),如果str[i...j]是回文串,那么dp[i]的值可能是dp[j+1]+1,其含义是在str[i...len-1]上,
 *   既然str[i...j]是一个回文串,那么它可以自己作为一个分割的部分,剩下的部分(即str[j+1...len-1])继续做最经济的分割,而dp[j+1]值的含义
 *   正好是str[j+1...len-1]的最少回文分割数
 * 2.根据步骤1的方式,让j在i到len-1位置上枚举,那么所有可能情况中的最小值就是dp[i]的值,
 *   即dp[i]=min{dp[j+1]+1 (i<=j<len,且str[i...j]必须是回文)}
 * 3.判断str[i...j]是否是回文串
 *   1)定义数组boolean[][] p,如果p[i][j]值为true,说明字符串str[i...j]是回文串,否则不是.
 *   2)p[i][j]如果为true,一定是一下三种情况:
 *     str[i...j]由1个字符组成
 *     str[i...j]由2个字符组成且2个字符相等
 *     str[j+1...j-1]是回文串,即p[i+1][j-1]true,且str[i]==str[j],即str[i...j]上首尾两个字符相等
 *   3)在计算dp数组的过程中,位置i是从右向左依次计算的.而对于每一个i来说,又依次从i位置向右枚举所有的位置j(i<=j<len),以此来决策出dp[i]的
 *     值.所以对p[i][j]来说,p[i+1][j-1]值一定已经计算过.
 * 4.最终返回dp[0]的值.
 */
public class 回文字符串分割数 {

    public static void main(String[] args) {
        System.out.println(minCut("ABA"));
        System.out.println(minCut("ACDCDCDAD"));
    }

    public static int minCut(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chars = str.toCharArray();
        int len = chars.length;
        int[] dp = new int[len + 1];
        dp[len] = -1;
        boolean[][] p = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j] && (j - i < 2 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
}
